1. Field of the Invention
The invention relates to the automation of asynchronous circuit designs, and more specifically to the generation and implementation of hazard-free asynchronous circuit designs.
2. Background of the Invention
Races and Hazards in Asynchronous Circuits
Problems specific to the design of asynchronous control circuits are races and hazards. In general, a race-free asynchronous circuit is a circuit that will always respond as specified given enough time. That is, if the inputs of the circuit are frozen, and the outputs are observed after all internal switchings have occurred, then the specified output values are always observed. Race-freeness is a necessary condition for a correct asynchronous circuit.
A hazard-free asynchronous circuit is a circuit in which the specified output values are continuously observed and no unexpected values are intermittently observed. This is, if the inputs of the circuit are frozen, the specified output values are continuously observed. Hazard-freeness is also a necessary condition for a correct asynchronous circuit.
Modeling Asynchronous Circuits
Because time is not used to pace the operation of an asynchronous circuit, the specification and correct implementation of an asynchronous circuit design is quite complex. Events, signal transitions, or alternative indicia are generally used as pacers in models where implicit clocks are not part of the semantics.
Signal transition graphs (STGs) are used as a formal basis for the automatic synthesis of asynchronous designs. State graphs (SGs) represent a general model where low level circuit details become more evident. SGs are a generally accepted low level form of representation with well defined semantics that capture every possible event occurrence. Because of the simplicity behind the SG semantics, SGs provide a strong basis to formalize asynchronous circuit properties and to derive clear links between the SG representation and its implementation (i.e., in a circuit design). As is conventionally known in the art, an STG can be transformed into an SG (see, e.g., T. A. Chu, "Synthesis of self-timed VLSI circuits from graph-theoretic specifications", Ph.D. thesis, MIT, June 1987, hereinafter Chu Thesis).
Informally, an SG has the following basic properties:
1) Any two consecutive states always differ by one and only one bit. PA1 2) The time it takes to make a state transition is any finite non-zero time. PA1 3) A state transition represents an input or an output event. PA1 4) An event is simply a (0 to 1) or a (1 to 0) signal change. SGs are more formally defined in Appendix A.
FIGS. 1a through 1d show a typical asynchronous circuit design path. First, a high-level description of the asynchronous process in the form of a timing diagram is given. In the example of FIG. 1a, a handshaking status generator timing diagram is shown with inputs signals a and c, and output signal b. In FIG. 1b, an STG is generated from the timing diagram in FIG. 1a. In FIG. 1c(1), an SG is conventionally generated from the STG in FIG. 1b (or directly from the timing diagram in 1a). Each state transition of the SG captures one possible event occurrence. The SG can be mechanically generated from the STG. In the example of FIG. 1c(1), a code conflict occurs at state 001 (explained below) and is resolved by adding a signal as shown in FIG. 1c(2). A hazard-free circuit can then be derived from the SG as shown in FIG. 1d.
Implementation of Models
To implement an SG (e.g., in a circuit), the states of an SG are interpreted as the states of the domain of a Boolean function that implements an output signal. The output signal can be implemented using pure logic or latches.
Logic can be derived for each output signal in an SG by considering at each state the next state value of the output signal, which is called the implied value. For example, an SG for an asynchronous process with input signals a and b, and output signals c and d is shown in FIG. 2a. At state s.sub.-- 3, the implied value of d is ONE. At state s.sub.-- 9, the implied value of d is ZERO. FIG. 2b is a Karnaugh map with the implied values for signal d. "DON'T CARES" are assigned to the unreachable states (i.e., 1100, 0011)--these are states that are not specified in the SG. Thus, from the Karnaugh map, signal d can be represented logically as d=ab+b({character pullout}c)+ad. The logic representation can be conventionally implemented in a logic circuit.
Another way to implement signal d is to use an asynchronous flip-flop or so-called C-element. The flip-flop has a SET input, a RESET input, and an output, OUT. The flip-flop implements the output signal. As a flip-flop is a memory, it suffices to only generate the logic to either set or reset it. The output signal is implemented with two auxiliary Boolean functions where one is used to set the flip-flop to generate d+(SET) and the other is used to reset the flip-flop to produce d-(RESET). These auxiliary Boolean functions are called SET and RESET functions or solutions. The implementation of the output signal corresponds to the implementation of the SET and RESET functions. The Boolean functions SET and RESET are generally expressed in sum-of-product (SOP) format.
FIG. 2c is an example Karnaugh map of a flip-flop-based solution to the SG in FIG. 2a. For the SET Boolean function, it suffices to consider the implied value for output signal d as ONE only at states s.sub.-- 3 and s.sub.-- 6. It is only at these states that d+ must be fired. At all other states where the implied value of d is ONE, a DON'T CARE is assigned. This assignment corresponds to the fact that after d+ is produced, the flip-flop will keep d at ONE in place of the logic. A ZERO is assigned to all states where the implied value of d is ZERO and DON'T CARES to all unreachable states. The RESET Boolean function is similarly derived to fire d-. The SET and RESET functions are then implemented in logic to drive the asynchronous flip-flop to implement the signal d as figuratively shown in FIG. 2c.
For the flip-flop-based solution, a number of states that were assigned a ONE in the pure logic derivation are now assigned DON'T CARES. A flip-flop has the effect of producing additional DON'T CARE states other than the unreachable states. In a pure logic derivation, DON'T CARE states correspond to the unreachable states (or non-specified states) in an SG. In a flip-flop-based derivation, DON'T CARE states correspond to the unreachable state set plus all states where a signal is stable. Thus, flip-flop-based solutions are preferred because of the availability of a larger DON'T CARE set.
Unfortunately, simply deriving the logic or flip-flop-based solutions from SGs as described does not guarantee that the derived circuit is correct. Races and hazards must be eliminated.
Prior Art Failures
One approach is to use complex gates to implement a hazard-free solution. However, the use of complex gates gives rise to new practical problems. As a complex gate is primarily a parallel-serial transistor network, as the complexity of the network grows, so does the number of serial N or P transistors. This significantly slows down in the response of the complex gate. In practice, only integration of simple two-level logic e.g., AND-NORs or OR-NANDs, are available in complex gates. Even if more complex gates are available, an enormous number of complex gate instances are required to cover any possible configuration. In general, a custom design is required for every race-free SG specified.
An improved solution is to substitute derived complex gates with a logic network composed of basic gates (e.g., NANDs, NORs, ANDs, ORs, negation). An architecture is fixed based on an asynchronous C-element flip-flop, and a simplified logic network is constructed from the complex solution to drive the flip-flop. However, a hazard-free network is only guaranteed for the limited class of race-free distributive SGs (distributivity, as defined below, informally means a restriction in the way concurrency can be represented). Even within this class of SGs, a solution is not guaranteed to be found without transforming the SG into a new SG by adding signals.
Another approach is to impose a so-called Monotonous Cover (MC) requirement on the SG. In general, MC ensures that one and only one gate switches at a time in order to fire an output signal. In this case no hazards can be produced because there is no second gate being turned ON-the hazardous mechanism is never triggered. However, under the MC requirement, the given architecture can only solve a the limited class of distributive semi-modular SGs.
In another solution, hazards are accounted for during the transient response by correcting the delay response of each cell such that hazards are avoided. This approach is based on the assumption that given a library of cells, each cell has a delay variation range associated with it that is well characterized and guaranteed by the foundry specifications. Transient responses can be corrected by adding delay lines in specific points in order to eliminate hazards. However, this delay insertion method relies on the fact that the delay requirements are one sided inequalities. That is, the problem can be solved when one path needs to be slower than the other to eliminate hazards. However, if double sided inequalities exist, i.e., one path has to be both slower than a first path and faster than a second path, the problem can not be solved.
The so-called Burst Mode Finite State Machines (FSMs), uses the principle that at certain specified states, the environment is stable long enough such that every gate stabilizes. The fact that the environment is stable long enough at some states eliminates some of the potential hazards. Then, necessary and sufficient conditions to eliminate remaining hazards are constructed. However, the environmental conditions correspond to implicit timing constraints added to the environment. These assumed timing constraints can only be checked to be valid after a circuit is generated to verify whether the actual timing of the environment does guarantee internal circuit stabilization at all states where it was assumed to eliminate hazards.
In summary, the prior art approaches attempt to eliminate hazards by manipulating and restricting the logic solution in order to account for asynchronous properties represented in the SG (or STG, CD, or other formal model). Under the imposed restrictions a solution may not exist. The restrictions are generally expressed as graph properties that must be present in the SG in order to derive a hazard-free implementation (e.g., MC requirement). If the SG does not conform to the restrictions imposed to it, then it must be transformed into a new one. This process continues until the final SG satisfies the restrictions. Convergence of such a loop is not guaranteed. Also, the transformations may not lead to an optimal solution, but rather to larger and slower circuits, or to no solution at all. The various methods differ in the degree of the restrictions that are imposed on the SG and on how the architecture is considered. The prior art methods for eliminating hazards in the implementation of asynchronous circuits have not reached a solution in a feasible or practical manner.
It would be desirable to define an architecture (e.g., a flip-flop) that implements an optimal hazard-free circuit without imposing significant restrictions on the SG representation or using complex logic implementations. In addition, it would be advantageous to use existing synchronous logic circuit minimization, optimization, mapping, routing, and synthesis tools to derive the asynchronous logic functions (e.g., SET and RESET) of the architecture, i.e., use synchronous logic CAD tools to derive asynchronous circuits.